1. Field of the Invention
This invention relates to electronic processing systems, and more particularly to an electronic system for manipulating data representing geometrical objects and related information in a computer graphics display system.
2. Background Information
The synthesis of visual scenes through the use of computers (computer graphics) is a growing area of computer science. There are innumerable applications of computer graphics, including computer-aided design (CAD), the synthesis of demonstrative charts, creation of titles and other graphics displays for television use, and the simulation of physical events.
In order to facilitate the generation of a scene including one or more objects by computer, normally the first step is to create a three-dimensional description of the objects to be displayed and to store them in mathematical form in a graphics data base. The data is then processed and manipulated so that the scene can be imaged on a display screen.
The processing of information from a graphics data base can be thought of as involving four basic functions:
1. Extracting data corresponding to some part of a graphics object from the graphics data base;
2. Determining which areas of the graphics object are to be visible on the display screen;
3. Transforming the three-dimensional description of the graphics object to a two-dimensional description in display screen coordinates; and
4. Selecting the pixels of the display screen which must be activated to display the object, defining their color and intensity, and activating them to form the desired graphics image.
The present invention is concerned with the second and third processing steps.
One format for storing a graphics data base is referred to as a "hierarchical display list", in which graphics data describing various objects (or pieces of objects) are stored in "segments". Each segment can be thought of as representing a graphics object. Each segment can have one or more segments associated with it in a "parent-child" relationship. The child segment of a parent segment may in turn have one or more child segments associated with it. This parent-child relationship between segments results in a hierarchical inverse "tree" structure.
Each segment of a hierarchical graphics data base typically has structural information which includes "pointers" to parent, child, and "sibling" segments. Sibling segments are those segments having the same parent segment. A pointer to a segment identifies the starting location of that segment in a computer system memory or storage device. In addition to the hierarchical structural data, each segment may also contain a graphics primitive and attributes of the primitive. A graphics primitive is typically a simple planar object, such as a polygon or a vector, defined by a list of coordinates in a convenient three-dimensional coordinate system for that particular graphics primitive. Attribute data for a graphics primitive may define the color or other characteristics of the primitive, and may also include a transformation matrix which specifies the spatial position and orientation of the graphics primitive of that segment with respect to the coordinate system of its parent segment. A feature of one type of hierarchical graphic data base is that attribute information, if not different from the parent segment, need not be defined in the child segment, but can instead be "inherited" from the parent segment.
Computer systems often include peripheral processors to increase the computational speed of the overall system. Peripheral processors are typically specialized computational systems designed to efficiently perform one or more functions. One such peripheral processor is a graphics processor which is designed to accept data from a graphics data base, select portions of that data to be further processed, perform the further processing, and transfer the processed data to another special purpose processor for display on a display screen.
Such graphics processors are used in a variety of applications. For example, interactive CAD systems often utilize graphics processors in conjunction with a host computer to store and display a model of the object or objects to be designed. A designer directs the system through various input devices to create the model, often on a piece-by-piece basis. The various pieces of the model form a graphics data base which is stored by the graphics processor and displayed on command. Changes to the model by the designer cause the system to modify the data base and update the display screen to image the modified model.
An appropriately designed graphics processor, in response to commands from a host computer, can create, copy, or delete segments of a hierarchical data base, which is typically stored in a separate memory of the graphics processor. The graphics processor further can delete, add, or modify various graphics data (such as the attributes, graphics primitives, and transformation matrix within each segment of the graphics data base) in response to host level commands. Once the hierarchical data base has been completed, the graphics processor reads and processes the graphics data base, producing images on a display screen of the objects represented by the graphics data base, as viewed through a user-defined "viewport". In reading the graphics data base, the graphics processor "traverses" the data base by reading data from a first segment of the data base and then moving to a relative segment (either parent, child, or sibling) identified by the first segment's pointers, in accordance with a traversal algorithm. In this manner, the graphics processor traverses the segment "tree" until the data in the graphics data base has been processed.
Because graphics processing is an extremely computation intensive processing task, in order to process the graphics data base in a reasonable amount of time, a peripheral graphics processor may employ a number of special purpose subprocessors to perform separate portions of the overall task. One such subprocessor is a geometry processor.
A sophisticated geometry processor can perform a number of processing function on the graphics data base of the segments. One important function is to test the graphics primitives of each segment to determine whether the primitives are within the field of view defined by the viewport. If not, the segment, and all of its children segments, can be ignored for purposes of further processing, thus increasing overall processing speed.
Additional geometry processor functions can include concatenation of transformation matrices to produce a transformation matrix for each segment which can transform the graphics primitive coordinate set of the segment into the coordinate set of the viewport segment at the "top" of the inverted tree structure. Also, the geometry processor can "clip" partially visible graphics primitives so that those portions of any primitives extending outside the field of view are not processed.
Graphics primitives which are defined in three dimensions must be projected to the two-dimensional image plane of the display. Two principal projection techniques are parallel projection and perspective projection. Parallel projection can be performed by simply ignoring the third coordinate (depth) of the three dimensional coordinate set. Perspective projection can be performed by dividing the components of the first two coordinates (height and width) by the third component (depth) to give the effect of a diminishment in size for those primitives which are "farther" from the viewer.
Once a graphics primitive has been clipped, projected, and/or otherwise transformed, a geometry processor can convert the coordinates of the primitive to the "hardware coordinates" used to display the primitives on a display screen. From the hardware coordinates, the primitives are "rasterized" by a display processor, which converts the hardware coordinates of the primitives into a collection of pixels. Once a primitive has been rasterized, hidden surfaces caused by overlapping primitives are removed.
It can be appreciated from the above that an extensive amount of calculation is often required to process and display the graphics primitive of a segment. Complex models can encompass a data base of thousands of segments. As a result, a graphics processor can require a significant amount of time to convert the data in a graphics data base into an image on a screen. Thus, it is desirable to develop a graphics processor architecture having a very high graphics processing speed. It is further desirable to develop a graphics processor architecture that uses a multitude of subprocessors to divide the complex task of processing a graphics data base into an image in order to achieve higher efficiencies and processing speed. It is therefore desirable to develop a high-speed graphics geometry processor to share the task of processing a graphics data base.
The present invention accomplishes these and other objects by means of a geometry processor having a novel internal processing architecture and system architecture that permits fast and efficient processing of a graphics data base with a simple yet powerful design.